package com.zhanghp.class012;

import com.zhanghp.common.ListNode;
import com.zhanghp.common.PrintUtil;

/**
 * 给你一个链表的头节点 head 和一个特定值 x
 * 请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
 * 你应当 保留 两个分区中每个节点的初始相对位置
 * 测试链接 : https://leetcode.cn/problems/partition-list/
 *
 * @author zhanghp
 * @since 2024/2/21 17:16
 */
public class PartitionList {

    static class Solution {

        // 1 4 3 2 5 2
        // l: 1
        // r: 4
        public static void main(String[] args) {
            ListNode listNode = new ListNode(1);
            listNode.next = new ListNode(4);
            listNode.next.next = new ListNode(3);
            listNode.next.next.next = new ListNode(2);
            listNode.next.next.next.next = new ListNode(5);
            listNode.next.next.next.next.next = new ListNode(2);
            int x = 3;
            ListNode partition = partition(listNode, x);
            PrintUtil.printListNode(partition);
        }

        public static  ListNode partition(ListNode head, int x) {
            ListNode leftHead = null, leftTail = null,
                    rightHead = null, rightTail = null;
            while (head != null) {
                if(head.val < x){
                    if (leftHead == null) {
                        leftHead = head;
                    }else {
                        // 给head下一值设值
                        leftTail.next = head;
                    }
                    leftTail = head;
                }else {
                    if (rightHead == null) {
                        rightHead = head;
                    }else {
                        rightTail.next = head;
                    }
                    rightTail = head;
                }
                head = head.next;
            }
            if (leftHead == null) {
                return rightHead;
            }
            leftTail.next = rightHead;
            return leftHead;
        }
    }
}
